/**
//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：digits = "23"
//输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 
//
// 示例 2： 
//
// 
//输入：digits = ""
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：digits = "2"
//输出：["a","b","c"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= digits.length <= 4 
// digits[i] 是范围 ['2', '9'] 的一个数字。 
// 
// Related Topics 哈希表 字符串 回溯 👍 1796 👎 0

*/

package com.xixi.basicAlgroithms.backtracking;

import java.util.*;

public class ID00017LetterCombinationsOfAPhoneNumber {
public static void main(String[] args) {
Solution solution = new ID00017LetterCombinationsOfAPhoneNumber().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public Map<Character, char[]> numAlphas = new HashMap<>();

    public List<String> results = new ArrayList<>();

    public List<String> letterCombinations(String digits) {

        if(digits.length() ==0) return Collections.emptyList();

        numAlphas.put('2', new char[]{'a','b','c'});//2
        numAlphas.put('3', new char[]{'d','e','f'});//3
        numAlphas.put('4', new char[]{'g','h','i'});//4
        numAlphas.put('5', new char[]{'j','k','l'});//5
        numAlphas.put('6', new char[]{'m','n','o'});//6
        numAlphas.put('7', new char[]{'p','q','r','s'});//7
        numAlphas.put('8', new char[]{'t','u','v'});//8
        numAlphas.put('9', new char[]{'w','x','y','z'});//9

        backTracking(digits.toCharArray(), digits.length(),0, new char[digits.length()]);
        return results;



    }


    public void backTracking(char[] digitsChar, int digitsSize, int level, char[] pathArray){

        if(level == digitsSize){
            String result = String.valueOf(pathArray);
            results.add(result);
            return;
        }

        char[] alphaArray = numAlphas.get(digitsChar[level]);
        for(int i = 0; i < alphaArray.length; ++i){
            pathArray[level] = alphaArray[i];//画上
            backTracking(digitsChar,digitsSize, level +1, pathArray);
            //递归之后，擦掉，到下一个字母的循环
            pathArray[level] = '*';
        }

    }
}
//leetcode submit region end(Prohibit modification and deletion)




}